package Binary_tree;

public class Code01_MaxSumInTree {

    public static class Node{
        public int value;
        public Node left;
        public Node right;

        public Node(int val){
            value = val;
        }
    }

    // x为头的整棵树上，最大路径和是多少，返回。
    // 路径要求，一定从x出发，到叶节点，算做一个路径
    public static int process(Node x){
        if (x.left == null && x.right == null){
            return x.value;
        }
        // next表示左树和右树谁的路径和最大
        int next = Integer.MIN_VALUE;
        if (x.left != null){
            next = process(x.left);
        }
        if (x.right != null){
            next = Math.max(next, process(x.right));
        }
        return x.value + next;
    }

    public static void main(String[] args){
        Node head = new Node(4);
        head.left = new Node(1);
        head.left.right = new Node(5);
        head.right = new Node(-7);
        head.right.left = new Node(3);
        System.out.println(process(head));
    }
}
